//
// Created by LiuYou on 2021/12/1.
//

#include <iostream>
#include <vector>
#include <random>
#include <iterator>


/*
 * 这个函数的思想是荷兰国旗问题。
 */
static std::vector<int> partition(std::vector<int>& arr, int left, int right) {
    // < 区域右边界。
    int less = left - 1;
    // > 区域左边界。
    int more = right;
    // left 表示当前数的位置, arr[right] -> 划分值
    while (left < more) {
        if (arr[left] < arr[right]) {
            std::swap( arr[++less], arr[left++] );
        } else if (arr[left] > arr[right]) {
            std::swap( arr[--more], arr[left] );
        } else {
            left++;
        }
    }
    std::swap( arr[more], arr[right] );
    return std::vector<int>{less + 1, more};
}


static int randomNumberFromTheRange(int left, int right) {
    std::random_device randomDevice;
    std::default_random_engine randomEngine( randomDevice());
    std::uniform_int_distribution<> uniformIntDistribution( left, right );
    return uniformIntDistribution( randomEngine );
}


static void quickSort(std::vector<int>& arr, int left, int right) {
    if (left < right) {
        // 快排第一步: 等概率随机选一个位置, 把它和最右侧的数做交换。
        // todo 笔记: 下面这行代码有没有都是可以的。如果没有那么快排的时间复杂度就不一定是 O(nlogn)了, 只可能比 O(nlogn)更差,
        //  极端情况: 例如: 1234567 的话就是 O(n2)。所以为了快排的时间复杂度, 一定要随机选一个元素作为划分值。
        std::swap( arr[randomNumberFromTheRange( left, right )], arr[right] );
        // 返回的这个 p 数组, 长度一定为 2。
        // 它是区域的左边界和右边界的下标。
        std::vector<int> p = partition( arr, left, right );

        // p[0]是 = 区域的左边界。p[0] -1 , 即为 < 区域的右边界。
        // 在 < 区域递归。
        quickSort( arr, left, p[0] - 1 );
        // p[1]是 = 区域的右边界。p[1] + 1, 即为 > 区域的左边界。
        quickSort( arr, p[1] + 1, right );
    } else {
        return;
    }
}


static void quickSort(std::vector<int>& arr) {
    if (arr.empty() || arr.size() == 1) {
        return;
    }

    quickSort( arr, 0, arr.size() - 1 );
}


int main(int argc, char** argv) {
    std::vector<int> arr;
    arr.reserve( 10 );
    for (int i = 0; i < 10; ++i) {
        arr.push_back( randomNumberFromTheRange( 0, 100 ));
    }

    std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
    std::cout << std::endl;

    quickSort( arr );
    std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
    std::cout << std::endl;


    return 0;
}
